package net.tp.algo.text;

public class Anagram {

    /**
     * Find next anagram in lexical order.
     *
     * <p>
     * This is Dijkstra's algorithm to find the next anagram in the lexical order. See Dijkstra's A Discipline of Programming.
     *
     *
     * @param text the current anagram
     * @throws IndexOutOfBoundsException when there is no next anagram
     *
     */
    public static void nextLexicalAnagram(char[] text) {
        int n = text.length;
        int i = n - 2;
        while (text[i] >= text[i+1]) i--;

        int j = n - 1;
        while (text[j] <= text[i]) j--;

        swap(text, i, j);

        i++; j = n - 1;
        while (i < j) swap(text, i++, j--);
    }

    private static void swap(char[] text, int i, int j) {
        char c = text[i];
        text[i] = text[j];
        text[j] = c;
    }

}
